GATE CSE 2010
Q11.
A system has n resources R_{0},...R_{n-1}, and k processes P_{0},...P_{k-1}. The implementation of the resource request logic of each process P_{i} is as follows: if (i%2= = 0) { if (i\ltn) request R_{i} ; if (i+2\ltn)request R_{i+2}; } else { if (i\ltn) request R_{n-i}; if (i+2\ltn)request R_{n-i-2} ; } In which one of the following situations is a deadlock possible?Q12.
Consider the set S = {1, \omega ,\omega ^{2}}, where \omega and \omega ^{2} are cube roots of unity. If * denotes the multiplication operation, the structure (S, *) formsQ13.
A hash table of length 10 uses open addressing with hash function h(k)=k mod 10, and linear probing. After inserting 6 values into an empty hash table, the table is as shown below Which one of the following choices gives a possible order in which the key values could have been inserted in the table?Q14.
A hash table of length 10 uses open addressing with hash function h(k)=k mod 10, and linear probing. After inserting 6 values into an empty hash table, the table is as shown belowHow many different insertion sequences of the key values using the same hash function and linear probing will result in the hash table shown above?Q16.
The program below uses six temporary variables a, b, c, d, e, f. a =1 b= 10 c =20 d= a +b e= c +d f =c +e b= c+ e e =b +f d =5 +e return d +f Assuming that all operations take their operands from registers, what is the minimum number of registers needed to execute this program without spilling?Q17.
Which data structure in a compiler is used for managing information about variables and their attributes?Q18.
The following C function takes a simply-linked list as input argument. It modifies the list by moving the last element to the front of the list and returns the modified list. Some part of the code is left blank. typedef struct node { int value; struct node *next; } Node; Node *move_to_front(Node *head) { Node *p, *q; if ((head = = NULL: || (head->next = = NULL)) return head; q = NULL; p = head; while (p-> next !=NULL) { q=P; p=p->next; } _______________________________ return head; } Choose the correct alternative to replace the blank line.Q19.
A main memory unit with a capacity of 4 megabytes is built using 1Mx1-bit DRAM chips. Each DRAM chip has 1K rows of cells with 1K cells in each row. The time taken for a single refresh operation is 100 nanoseconds. The time required to perform one refresh operation on all the cells in the memory unit isQ20.
Consider a complete undirected graph with vertex set {0, 1, 2, 3, 4}. Entry W_{ij} in the matrix W below is the weight of the edge {i, j}. \begin{pmatrix} 0&1 & 8 & 1 &4 \\ 1& 0 & 12 & 4 & 9\\ 8 & 12 & 0 & 7 & 3\\ 1& 4& 7 & 0 &2 \\ 4& 9 & 3& 2 &0 \end{pmatrix}What is the minimum possible weight of a spanning tree T in this graph such that vertex 0 is a leaf node in the tree T?